
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Random;

public class DriversNetwork {

    /**
     * Creates a random network among the drivers based on the variation G(n, p)
     * of the Erdős–Rényi model.
     *
     * @param D set of drivers
     * @param p independent probability of an edge to exist among two given
     * nodes
     * @return the drivers network
     */
    public static <T extends Driver<T>> Graph random(ArrayList<T> D, double p) {

        Hashtable<String, Vertex> V = new Hashtable<String, Vertex>();
        Hashtable<String, Edge> E = new Hashtable<String, Edge>();

        Random rand = new Random(Params.RANDOM.nextInt());

        //create vertices from drivers
        for (T d : D) {
            V.put(String.valueOf(d.getId()), new Vertex(String.valueOf(d.getId())));
        }

        //for each pair of vertices, create an edge between them with probability p
        for (T d1 : D) {
            for (T d2 : D) {//.subList((int)d1.getId()-1, D.size())
                if (d1.getId() < d2.getId()) {
                    if (rand.nextDouble() < p) {
                        String id = new String("" + d1.getId() + d2.getId());
                        E.put(id, new Edge(
                                id,
                                V.get(String.valueOf(d1.getId())),
                                V.get(String.valueOf(d2.getId())),
                                0,
                                true //undirected,
                                ,0,0,0
                        ));
                    }
                }
            }
        }

        return new Graph(V, E, false);
    }

    /**
     * Creates a small-world network among the drivers based on the
     * Watts–Strogatz model.
     *
     * @param D set of drivers
     * @param k the mean conectivity degree
     * @param beta a randomness parameter for rewiring edges
     * @return the drivers network
     */
    public static <T extends Driver<T>> Graph smallWorld(ArrayList<T> D, int k, double beta) {
        Hashtable<String, Vertex> V = new Hashtable<String, Vertex>();
        Hashtable<String, Edge> E = new Hashtable<String, Edge>();

        Random rand = new Random(Params.RANDOM.nextInt());

        k = k / 2;

        //create vertices from drivers
        for (T d : D) {
            V.put(String.valueOf(d.getId()), new Vertex(String.valueOf(d.getId())));
        }

        //create a circular lattice where each node is connected with its k nearest neighbours (k/2 on each side)
        for (int i = 0; i < D.size(); i++) {
            T d1 = D.get(i);

            for (int i2 = i - k; i2 <= i + k; i2++) {
                if (i2 != i) {
                    int i2_aux = (i2 < 0) ? (D.size() + i2) : ((i2 > D.size() - 1) ? i2 - D.size() : i2);
                    if (i2_aux < i) {
                        continue;
                    }

                    T d2 = D.get(i2_aux);
                    String id = new String("" + d1.getId() + d2.getId());
                    E.put(id, new Edge(
                            id,
                            V.get(String.valueOf(d1.getId())),
                            V.get(String.valueOf(d2.getId())),
                            0,
                            true //undirected
                            ,0,0,0
                    ));

                }
            }

        }

        //rewire edges with probability p
        for (Edge e : E.values()) {
            if (rand.nextDouble() < beta) {

                ArrayList<Vertex> allowed = new ArrayList<Vertex>();
                for (Vertex v : V.values()) {
                    allowed.add(v);
                }
                allowed.remove(e.getFrom());
                allowed.removeAll(e.getFrom().getNeighbours());

                if (allowed.isEmpty()) {
                    continue;
                }
                e.getTo().removeEdgesWith(e.getFrom());
                e.setTo(allowed.get(rand.nextInt(allowed.size())));
                e.getTo().addInEdge(e);

            }
        }

        return new Graph(V, E, false);
    }

    /**
     * Creates a small-world network among the drivers based on the
     * Barabási–Albert model.
     *
     * @param D set of drivers
     * @param m number of edges created for each new node
     * @return the drivers network
     */
    public static <T extends Driver<T>> Graph scaleFree(ArrayList<T> D, int m) {
        Hashtable<String, Vertex> V = new Hashtable<String, Vertex>();
        Hashtable<String, Edge> E = new Hashtable<String, Edge>();

        Random rand = new Random(Params.RANDOM.nextInt());

        for (T d : D) {
            Vertex new_node = new Vertex(String.valueOf(d.getId()));
            V.put(new_node.getId(), new_node);

            if (V.size() == 1) {
                continue;
            } else if (V.size() <= 2) {
                Vertex v1 = (Vertex) V.values().toArray()[0];
                Vertex v2 = (Vertex) V.values().toArray()[1];

                String id = new String("" + v1.getId() + v2.getId());
                E.put(id, new Edge(
                        id,
                        V.get(String.valueOf(v1.getId())),
                        V.get(String.valueOf(v2.getId())),
                        0,
                        true //undirected
                        ,0,0,0
                ));

            } else {
                double degreeSum = E.size() * 2;

                int count = 0;
                out:
                do {

                    for (Vertex v : V.values()) {
                        if (!v.getId().equals(new_node.getId()) && !new_node.getNeighbours().contains(v)) {
                            if (rand.nextDouble() < (v.getNeighbours().size() / degreeSum)) {
                                String id = new String("" + new_node.getId() + v.getId());
                                E.put(id, new Edge(
                                        id,
                                        V.get(String.valueOf(new_node.getId())),
                                        V.get(String.valueOf(v.getId())),
                                        0,
                                        true //undirected
                                        ,0,0,0
                                ));
                                count++;
                                if (count >= m) {
                                    break out;
                                }
                            }
                        }
                    }

                } while (count < m);
            }
        }

        return new Graph(V, E, false);
    }

    /**
     * Populates the drivers' list of neighbours according to the generated
     * social network.
     *
     * @param D the set of drivers
     * @param S the generated social network
     */
    public static <T extends Driver<T>> void updateDrivers(ArrayList<T> D, Graph S) {
        Hashtable<String, T> HD = new Hashtable<String, T>();
        for (T d : D) {
            HD.put(String.valueOf(d.getId()), d);
        }
        //System.out.println(HD);
        for (T d : D) {
            ArrayList<T> n = new ArrayList<T>();
            for (Vertex v : S.getVertex(String.valueOf(d.getId())).getNeighbours()) {
                n.add(HD.get(v.getId()));
            }
            d.setNeighbours(n);
        }

        /*for (Driver d : D) {
         System.out.println(d + " = " + d.getNeighbours());
         }/**/
    }

}
